/*
 * @lc app=leetcode id=134 lang=cpp
 *
 * [134] Gas Station
 */
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int gasLen = gas.size();
        int costLen = cost.size();
        if (gasLen != costLen || gasLen < 1) {
            return -1;
        }

        for (int startIdx=0; startIdx < gasLen; startIdx++) {
            if (gas[startIdx] < cost[startIdx]) {
                continue;
            }

            int v = gas[startIdx] - cost[startIdx];
            int i=(startIdx+1)%gasLen;
            for (; i!=startIdx; i=(i+1)%gasLen) {
                v += gas[i]-cost[i];
                if (v < 0) {
                    break;
                }
            }
            if (v >= 0 && i == startIdx) {
                return i;
            }
        }
        return -1;
        
    }
};

